﻿Cluster analysis or clustering is the assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense. Clustering is a method of unsupervised learning, and a common technique for statistical data analysis used in many fields, including machine learning, data mining, pattern recognition, image analysis, information retrieval, and bioinformatics.

Besides the term clustering, there are a number of terms with similar meanings, including automatic classification, numerical taxonomy, botryology and typological analysis.

Contents [hide]
1 Types of clustering 
2 Distance measure 
3 Hierarchical clustering 
3.1 Agglomerative hierarchical clustering 
3.2 Concept clustering 
4 Partitional clustering 
4.1 K-means and derivatives 
4.1.1 k-means clustering 
4.1.2 Fuzzy c-means clustering 
4.1.3 QT clustering algorithm 
4.2 Locality-sensitive hashing 
4.3 Graph-theoretic methods 
5 Spectral clustering 
6 Applications 
6.1 Biology 
6.2 Medicine 
6.3 Market research 
6.4 Educational research 
6.4.1 Example of cluster analysis in educational research 
6.4.2 Common cluster techniques in educational research 
6.4.3 Advantages of cluster analysis 
6.4.4 Disadvantages of cluster analysis 
6.4.5 Solution to problems of cluster analysis in educational research 
6.5 Other applications 
7 Evaluation of clustering 
7.1 Internal criterion of quality 
7.2 External criterion of quality 
7.3 Relative criterion of quality 
8 Algorithms 
9 See also 
10 References 
11 Further reading 
 
[edit] Types of clusteringHierarchical algorithms find successive clusters using previously established clusters. These algorithms usually are either agglomerative ("bottom-up") or divisive ("top-down"). Agglomerative algorithms begin with each element as a separate cluster and merge them into successively larger clusters. Divisive algorithms begin with the whole set and proceed to divide it into successively smaller clusters.

Partitional algorithms typically determine all clusters at once, but can also be used as divisive algorithms in the hierarchical clustering.

Density-based clustering algorithms are devised to discover arbitrary-shaped clusters. In this approach, a cluster is regarded as a region in which the density of data objects exceeds a threshold. DBSCAN and OPTICS are two typical algorithms of this kind.

Subspace clustering methods look for clusters that can only be seen in a particular projection (subspace, manifold) of the data. These methods thus can ignore irrelevant attributes. The general problem is also known as Correlation clustering while the special case of axis-parallel subspaces is also known as Two-way clustering, co-clustering or biclustering: in these methods not only the objects are clustered but also the features of the objects, i.e., if the data is represented in a data matrix, the rows and columns are clustered simultaneously. They usually do not however work with arbitrary feature combinations as in general subspace methods. But this special case deserves attention due to its applications in bioinformatics.

Many clustering algorithms require the specification of the number of clusters to produce in the input data set, prior to execution of the algorithm. Barring knowledge of the proper value beforehand, the appropriate value must be determined, a problem on its own for which a number of techniques have been developed.

[edit] Distance measureAn important step in most clustering is to select a distance measure, which will determine how the similarity of two elements is calculated. This will influence the shape of the clusters, as some elements may be close to one another according to one distance and farther away according to another. For example, in a 2-dimensional space, the distance between the point (x = 1, y = 0) and the origin (x = 0, y = 0) is always 1 according to the usual norms, but the distance between the point (x = 1, y = 1) and the origin can be 2,  or 1 if you take respectively the 1-norm, 2-norm or infinity-norm distance.

Common distance functions:

The Euclidean distance (also called distance as the crow flies or 2-norm distance). A review of cluster analysis in health psychology research found that the most common distance measure in published studies in that research area is the Euclidean distance or the squared Euclidean distance. 
The Manhattan distance (aka taxicab norm or 1-norm) 
The maximum norm (aka infinity norm) 
The Mahalanobis distance corrects data for different scales and correlations in the variables 
The angle between two vectors can be used as a distance measure when clustering high dimensional data. See Inner product space. 
The Hamming distance measures the minimum number of substitutions required to change one member into another. 
Another important distinction is whether the clustering uses symmetric or asymmetric distances. Many of the distance functions listed above have the property that distances are symmetric (the distance from object A to B is the same as the distance from B to A). In other applications (e.g., sequence-alignment methods, see Prinzie & Van den Poel (2006)), this is not the case. (A true metric gives symmetric measures of distance.)

[edit] Hierarchical clusteringMain article: Hierarchical clustering
 It has been suggested that this article or section be merged into Hierarchical clustering. (Discuss) 

Hierarchical clustering creates a hierarchy of clusters which may be represented in a tree structure called a dendrogram. The root of the tree consists of a single cluster containing all observations, and the leaves correspond to individual observations.

Algorithms for hierarchical clustering are generally either agglomerative, in which one starts at the leaves and successively merges clusters together; or divisive, in which one starts at the root and recursively splits the clusters.

Any valid metric may be used as a measure of similarity between pairs of observations. The choice of which clusters to merge or split is determined by a linkage criterion, which is a function of the pairwise distances between observations.

Cutting the tree at a given height will give a clustering at a selected precision. In the following example, cutting after the second row will yield clusters {a} {b c} {d e} {f}. Cutting after the third row will yield clusters {a} {b c} {d e f}, which is a coarser clustering, with a smaller number of larger clusters.

[edit] Agglomerative hierarchical clusteringFor example, suppose this data is to be clustered, and the euclidean distance is the distance metric.

 
Raw data
The hierarchical clustering dendrogram would be as such:

 
Traditional representation
This method builds the hierarchy from the individual elements by progressively merging clusters. In our example, we have six elements {a} {b} {c} {d} {e} and {f}. The first step is to determine which elements to merge in a cluster. Usually, we want to take the two closest elements, according to the chosen distance.

Optionally, one can also construct a distance matrix at this stage, where the number in the i-th row j-th column is the distance between the i-th and j-th elements. Then, as clustering progresses, rows and columns are merged as the clusters are merged and the distances updated. This is a common way to implement this type of clustering, and has the benefit of caching distances between clusters. A simple agglomerative clustering algorithm is described in the single-linkage clustering page; it can easily be adapted to different types of linkage (see below).

Suppose we have merged the two closest elements b and c, we now have the following clusters {a}, {b, c}, {d}, {e} and {f}, and want to merge them further. To do that, we need to take the distance between {a} and {b c}, and therefore define the distance between two clusters. Usually the distance between two clusters  and  is one of the following:

The maximum distance between elements of each cluster (also called complete linkage clustering): 
 
The minimum distance between elements of each cluster (also called single-linkage clustering): 
 
The mean distance between elements of each cluster (also called average linkage clustering, used e.g. in UPGMA): 
 
The sum of all intra-cluster variance. 
The increase in variance for the cluster being merged (Ward's criterion). 
The probability that candidate clusters spawn from the same distribution function (V-linkage). 
Each agglomeration occurs at a greater distance between clusters than the previous agglomeration, and one can decide to stop clustering either when the clusters are too far apart to be merged (distance criterion) or when there is a sufficiently small number of clusters (number criterion).

[edit] Concept clusteringAnother variation of the agglomerative clustering approach is conceptual clustering.

[edit] Partitional clustering[edit] K-means and derivatives[edit] k-means clusteringMain article: k-means clustering
The k-means algorithm assigns each point to the cluster whose center (also called centroid) is nearest. The center is the average of all the points in the cluster — that is, its coordinates are the arithmetic mean for each dimension separately over all the points in the cluster.

Example: The data set has three dimensions and the cluster has two points: X = (x1,x2,x3) and Y = (y1,y2,y3). Then the centroid Z becomes Z = (z1,z2,z3), where ,  and . 
The algorithm steps are[1]:

Choose the number of clusters, k. 
Randomly generate k clusters and determine the cluster centers, or directly generate k random points as cluster centers. 
Assign each point to the nearest cluster center, where "nearest" is defined with respect to one of the distance measures discussed above. 
Recompute the new cluster centers. 
Repeat the two previous steps until some convergence criterion is met (usually that the assignment hasn't changed). 
The main advantages of this algorithm are its simplicity and speed which allows it to run on large datasets. Its disadvantage is that it does not yield the same result with each run, since the resulting clusters depend on the initial random assignments (the k-means++ algorithm addresses this problem by seeking to choose better starting clusters). It minimizes intra-cluster variance, but does not ensure that the result has a global minimum of variance. Another disadvantage is the requirement for the concept of a mean to be definable which is not always the case. For such datasets the k-medoids variants is appropriate. An alternative, using a different criterion for which points are best assigned to which centre is k-medians clustering.

[edit] Fuzzy c-means clusteringIn fuzzy clustering, each point has a degree of belonging to clusters, as in fuzzy logic, rather than belonging completely to just one cluster. Thus, points on the edge of a cluster, may be in the cluster to a lesser degree than points in the center of cluster. For each point x we have a coefficient giving the degree of being in the kth cluster uk(x). Usually, the sum of those coefficients for any given x is defined to be 1:

 
With fuzzy c-means, the centroid of a cluster is the mean of all points, weighted by their degree of belonging to the cluster:

 
The degree of belonging is related to the inverse of the distance to the cluster center:

 
then the coefficients are normalized and fuzzyfied with a real parameter m > 1 so that their sum is 1. So

 
For m equal to 2, this is equivalent to normalising the coefficient linearly to make their sum 1. When m is close to 1, then cluster center closest to the point is given much more weight than the others, and the algorithm is similar to k-means.

The fuzzy c-means algorithm is very similar to the k-means algorithm:[2]

Choose a number of clusters. 
Assign randomly to each point coefficients for being in the clusters. 
Repeat until the algorithm has converged (that is, the coefficients' change between two iterations is no more than , the given sensitivity threshold) : 
Compute the centroid for each cluster, using the formula above. 
For each point, compute its coefficients of being in the clusters, using the formula above. 
The algorithm minimizes intra-cluster variance as well, but has the same problems as k-means; the minimum is a local minimum, and the results depend on the initial choice of weights. The expectation-maximization algorithm is a more statistically formalized method which includes some of these ideas: partial membership in classes. It has better convergence properties and is in general preferred to fuzzy-c-means.

[edit] QT clustering algorithmQT (quality threshold) clustering (Heyer, Kruglyak, Yooseph, 1999) is an alternative method of partitioning data, invented for gene clustering. It requires more computing power than k-means, but does not require specifying the number of clusters a priori, and always returns the same result when run several times.

The algorithm is:

The user chooses a maximum diameter for clusters. 
Build a candidate cluster for each point by iteratively including the point that is closest to the group, until the diameter of the cluster surpasses the threshold. 
Save the candidate cluster with the most points as the first true cluster, and remove all points in the cluster from further consideration. Must clarify what happens if more than 1 cluster has the maximum number of points ? 
Recurse with the reduced set of points. 
The distance between a point and a group of points is computed using complete linkage, i.e. as the maximum distance from the point to any member of the group (see the "Agglomerative hierarchical clustering" section about distance between clusters).

[edit] Locality-sensitive hashingLocality-sensitive hashing can be used for clustering. Feature space vectors are sets, and the metric used is the Jaccard distance. The feature space can be considered high-dimensional. The min-wise independent permutations LSH scheme (sometimes MinHash) is then used to put similar items into buckets. With just one set of hashing methods, there are only clusters of very similar elements. By seeding the hash functions several times (e.g. 20), it is possible to get bigger clusters.[3]

[edit] Graph-theoretic methodsFormal concept analysis is a technique for generating clusters(called formal concepts) of objects and attributes, given a bipartite graph representing the relation between the objects and attributes. This technique was introduced by Rudolf Wille in 1984. Other methods for generating overlapping clusters (a cover rather than a partition) are discussed by Jardine and Sibson (1968) and Cole and Wishart (1970).

[edit] Spectral clusteringSee also: Kernel principal component analysis 
Given a set of data points A, the similarity matrix may be defined as a matrix S where Sij represents a measure of the similarity between points . Spectral clustering techniques make use of the spectrum of the similarity matrix of the data to perform dimensionality reduction for clustering in fewer dimensions.

One such technique is the Normalized Cuts algorithm by Shi-Malik, commonly used for image segmentation. It partitions points into two sets (S1,S2) based on the eigenvector v corresponding to the second-smallest eigenvalue of the Laplacian matrix

L = I ? D ? 1 / 2SD ? 1 / 2 
of S, where D is the diagonal matrix

Dii = ∑ Sij. 
 j  

This partitioning may be done in various ways, such as by taking the median m of the components in v, and placing all points whose component in v is greater than m in S1, and the rest in S2. The algorithm can be used for hierarchical clustering by repeatedly partitioning the subsets in this fashion.

A related algorithm is the Meila-Shi algorithm, which takes the eigenvectors corresponding to the k largest eigenvalues of the matrix P = SD ? 1 for some k, and then invokes another (e.g. k-means) to cluster points by their respective k components in these eigenvectors.

[edit] Applications[edit] BiologyIn biology clustering has many applications

In imaging, data clustering may take different form based on the data dimensionality. For example, the SOCR EM Mixture model segmentation activity and applet shows how to obtain point, region or volume classification using the online SOCR computational libraries. 
In the fields of plant and animal ecology, clustering is used to describe and to make spatial and temporal comparisons of communities (assemblages) of organisms in heterogeneous environments; it is also used in plant systematics to generate artificial phylogenies or clusters of organisms (individuals) at the species, genus or higher level that share a number of attributes 
In computational biology and bioinformatics: 
In transcriptomics, clustering is used to build groups of genes with related expression patterns (also known as coexpressed genes). Often such groups contain functionally related proteins, such as enzymes for a specific pathway, or genes that are co-regulated. High throughput experiments using expressed sequence tags (ESTs) or DNA microarrays can be a powerful tool for genome annotation, a general aspect of genomics. 
In sequence analysis, clustering is used to group homologous sequences into gene families. This is a very important concept in bioinformatics, and evolutionary biology in general. See evolution by gene duplication. 
In high-throughput genotyping platforms clustering algorithms are used to automatically assign genotypes. 
In QSAR and molecular modeling studies as also chemoinformatics 
[edit] MedicineIn medical imaging, such as PET scans, cluster analysis can be used to differentiate between different types of tissue and blood in a three dimensional image. In this application, actual position does not matter, but the voxel intensity is considered as a vector, with a dimension for each image that was taken over time. This technique allows, for example, accurate measurement of the rate a radioactive tracer is delivered to the area of interest, without a separate sampling of arterial blood, an intrusive technique that is most common today.

[edit] Market researchCluster analysis is widely used in market research when working with multivariate data from surveys and test panels. Market researchers use cluster analysis to partition the general population of consumers into market segments and to better understand the relationships between different groups of consumers/potential customers.

Segmenting the market and determining target markets 
Product positioning 
New product development 
Selecting test markets (see : experimental techniques) 
[edit] Educational researchIn educational research analysis, data for clustering can be students, parents, sex or test score. Clustering is an important method for understanding and utility of cluster[4] in educational research. Cluster analysis in educational research can be used for data exploration [5], cluster confirmation [6] and hypothesis testing [6]. Data exploration is used when there is little information about which schools or students will be grouped together [5]. It aims at discovering any meaningful clusters of units based on measures on a set of response variables. Cluster confirmation is used for confirming the previously reported cluster results [6]. Hypothesis testing is used for arranging cluster structure [6].

[edit] Example of cluster analysis in educational researchIn 2002, Hattie used cluster analysis in the project 'School Like Mine' [7] to compare students’ achievement in literacy and numeracy by the type of school they attended. 2707 majority and minority students in New Zealand are classified into different clusters according to school size, student ethnicity, region, size of civil jurisdiction and socioeconomic status for comparison. The cluster in this research is calculated across five dimensions, decile, region, size, minority and rurality. All schools are placed into one of twenty clusters that are used in the asTTle software[clarification needed] as a basis of student achievement comparison. The result shows that using the power of socioeconomic status to describe schools is analysed and found inadequate.

Euclidean distance was used as the clustering method in this research. Schools that are alike were clustered together. In addition, dendrogram. By clustering schools, Hattie suggested that school types had no significant relation with performance of schools.

[edit] Common cluster techniques in educational researchAll cluster techniques have two basic concerns: firstly, the measurement of similarity between individual profiles; and secondly, the use of that measure to form the groups or clusters. Brennan [8] described Iterative Relocation as the most important cluster technique in behavioral and educational research. It has been adopted at Lancaster to create typologies of pupils based on personality and behavioral items to identify types of students [9] and to isolate the skills considered to be important for certain grades of technologist in industry. Other similarity coefficients are available and the one chosen will depend upon the type of data gained.

The number of groups needs to be decided. This is often an arbitrary decision and the groupings are random. The analysis then proceeds by computing the group profile (or group centroid) of each group, which is the cumulative frequencies of all variables measured. Each individual should be compared with each of the group centroids. A number of formulae are available for measuring this similarity. Among others, Wishart [8] has found the error sum of squares, a measure of dissimilarity, to be one of the most successful coefficients for continuous data. When relocate or alters the composition of groups and recalculate the group centroids are completed, a new iteration cycle commences. This sequence of comparison and relocation continues until all individuals are in the group whose central profile is most similar to their own. The solution is then said to be stable. The analysis is then continued by reducing the number of groups by one (N-1). This is achieved by a fushion process whereby a measure of dissimilarity (error sum of squares) between all pairs of group centroids is calculated again. The two most similar groups are then combined to reduce one group. Recalculate the group centroids and repeat steps 2 and 3 until the solution is stable for the N-1 group level. This process can continue until the two level group is reached, at which point the analysis is complete.

[edit] Advantages of cluster analysisFrisvad of BioCentrum-DTU said that cluster analysis is a good way for quick review of data, especially if the objects are classified into many groups.[10] In the ‘Schools Like Mine’ example,[7] 23 clusters of schools with different properties were clearly clustered. It is easy for users to assign or nominate themselves into a cluster they would most like to compare with in a school cluster database[7] because each cluster is clearly named with understandable terms.

Cluster Analysis provides a simple profile of individuals [7]. Given a number of analysis units, for example school size, student ethnicity, region, size of civil jurisdiction and social economic status in this example, each of which is described by a set of characteristics and attributes. Cluster Analysis also suggests how groups of units are determined such that units within groups are similar in some respect and unlike those from other groups [11]

[edit] Disadvantages of cluster analysisAn object can be assigned in one cluster only.[7] For example in 'Schools Like Mine', schools are automatically assigned into the first twenty-two clusters. However, if schools want to compare themselves with integrated schools, they will have to manually assign themselves into cluster twenty-three. Data-driven clustering may not represent reality, because once a school is assigned to a cluster, it cannot be assigned to another one. Some schools may have more than one significant property or fall on the edge of two clusters.[7]

Clustering may have detrimental effects to teachers who work in low-decile schools, students who are educated in them, and parents who support them, by telling them the schools are classified as ineffective, when in fact many are doing well in some unique aspects that are not sufficiently illustrated by the clusters formed [7].

In k-means clustering methods, it is often requires several analysis before the number of clusters can be determined [12]. It can be very sensitive to the choice of initial cluster centres.[12]

[edit] Solution to problems of cluster analysis in educational researchHattie stated although Cluster analysis provides an easy way to make comparison between schools, no particular variable should be taken as the “short cut” for judging school quality[7].in order to overcome the unit reassignment issue, some researchers suggest a nonhierarchical cluster method which allows for reassignment of units from one cluster. This operates through an iterative partitioning k- means algorithm, where k denotes the number of clusters [6]. Nevertheless, to conduct a k-means analysis, the number of clusters needs to be specified at the start. This limits the exploratory power of cluster analysis.

Cluster Analysis has to be very carefully used in classifying schools into groups because results are heavily influenced by partial sampling, choice of clustering criteria and compositional variables, as well as cluster labeling. Like assigning schools into different bands, clustering may bring about unnecessary comparisons and inappropriate discriminations among schools, thereby adversely affecting students.[7]

[edit] Other applicationsSocial network analysis 
In the study of social networks, clustering may be used to recognize communities within large groups of people. 
Software evolution 
Clustering is useful in software evolution as it helps to reduce legacy properties in code by reforming functionality that has become dispersed. It is a form of restructuring and hence is a way of directly preventative maintenance. 
Image segmentation 
Clustering can be used to divide a digital image into distinct regions for border detection or object recognition. 
Data mining 
Many data mining applications involve partitioning data items into related subsets; the marketing applications discussed above represent some examples. Another common application is the division of documents, such as World Wide Web pages, into genres. 
Search result grouping 
In the process of intelligent grouping of the files and websites, clustering may be used to create a more relevant set of search results compared to normal search engines like Google. There are currently a number of web based clustering tools such as Clusty. 
Slippy map optimization 
Flickr's map of photos and other map sites use clustering to reduce the number of markers on a map. This makes it both faster and reduces the amount of visual clutter. 
IMRT segmentation 
Clustering can be used to divide a fluence map into distinct regions for conversion into deliverable fields in MLC-based Radiation Therapy. 
Grouping of Shopping Items 
Clustering can be used to group all the shopping items available on the web into a set of unique products. For example, all the items on eBay can be grouped into unique products. (eBay doesn't have the concept of a SKU) 
Recommender systems 
Recommender systems are designed to recommend new items based on a user's tastes. They sometimes use clustering algorithms to predict a user's preferences based on the preferences of other users in the user's cluster. 
Mathematical chemistry 
To find structural similarity, etc., for example, 3000 chemical compounds were clustered in the space of 90 topological indices.[13] 
Climatology 
To find weather regimes or preferred sea level pressure atmospheric patterns.[14] 
Petroleum Geology 
Cluster Analysis is used to reconstruct missing bottom hole core data or missing log curves in order to evaluate reservoir properties. 
Physical Geography 
The clustering of chemical properties in different sample locations. 
Crime Analysis 
Cluster analysis can be used to identify areas where there are greater incidences of particular types of crime. By identifying these distinct areas or "hot spots" where a similar crime has happened over a period of time, it is possible to manage law enforcement resources more effectively. 
Evolutionary algorithms 
Clustering may be used to identify different niches within the population of an evolutionary algorithm so that reproductive opportunity can be distributed more evenly amongst the evolving species or subspecies. 
[edit] Evaluation of clusteringEvaluation of clustering is sometimes referred to as Cluster validation.

There have been several suggestions for a measure of similarity between two clusterings. Such a measure can be used to compare how well different data clustering algorithms perform on a set of data. These measures are usually tied to the type of criterion being considered in assessing the quality of a clustering method.

[edit] Internal criterion of qualityClustering evaluation methods that adhere to internal criterion assign the best score to the algorithm that produces clusters with high similarity within a cluster and low similarity between clusters. One drawback of using internal criterion in cluster evaluation is that high scores on an internal measure do not necessarily result in effective information retrieval applications [15].

The following methods can be used to assess the quality clustering algorithms based on internal criterion:

Davies–Bouldin index 
The Davies-Bouldin index can be calculated by the following formula: 
 
where n is the number of clusters, cx is the centroid of cluster x, σx is the average distance of all elements in cluster x to centroid cx, and d(ci,cj) is the distance between centroids ci and cj. Since algorithms that produce clusters with low intra-cluster distances (high intra-cluster similarity) and high inter-cluster distances (low inter-cluster similarity) will have a low Davies-Bouldin index, the clustering algorithm that produces a collection of clusters with the smallest Davies–Bouldin index is considered the best algorithm based on this criteria. 
Dunn Index 
The Dunn index aims to identify dense and well-separated cluster. It is defined as the ratio between the minimal intra-cluster distance to maximal inter-cluster distance. For each cluster partition, the Dunn index can be calculated by the following formula [16]: 
 
where d(i,j) represents the distance between clusters i and j, and d'(k) measures the intra-cluster distance of cluster k. The inter-cluster distance d(i,j) between two clusters may be any number of distance measures, such as the distance between the centroids of the clusters. Similarly, the intra-cluster distance d'(k) may be measured in a variety ways, such as the maximal distance between any pair of elements in cluster k. Since internal criterion seek clusters with high intra-cluster similarity and low inter-cluster similarity, algorithms that produce clusters with high Dunn index are more desirable. 
[edit] External criterion of qualityClustering evaluation methods that adhere to external criterion compare the results of the clustering algorithm against some external benchmark. Such benchmarks consist of a set of pre-classified items, and these sets are often created by human (experts). Thus, the benchmark sets can be thought of as a gold standard for evaluation. These types of evaluation methods measure how close the clustering is to the predetermined benchmark classes. However, it has recently been discussed whether this is adequate for real data, or only on synthetic data sets with a factual ground truth, since classes can contain internal structure, the attributes present may not allow separation of clusters or the classes may contain anomalies.[17]

Some of the measures of quality of a cluster algorithm using external criterion include:

Rand measure 
The Rand index computes how similar the clusters (returned by the clustering algorithm) are to the benchmark classifications. One can also view the Rand index as a measure of the percentage of correct decisions made by the algorithm. It can be compute using the following formula: 
 
where TP is the number of true positives, TN is the number of true negatives, FP is the number of false positives, and FN is the number of false negatives. One issue with the Rand index is that false positives and false negatives are equally weighted. This may be an undesirable characteristic for some clustering applications. The F-measure addresses this concern. 
F-measure 
The F-measure can be used to balance the contribution of false negatives by weighting recall through a parameter . Let precision and recall be defined as follows: 
 
 
where P is the precision rate and R is the recall rate. We can calculate the F-measure by using the following formula [15]: 
 
Notice that when β = 0, F0 = P. In other words, recall has no impact on the F-measure when β = 0, and increasing β allocates an increasing amount of weight to recall in the final F-measure. 
Jaccard index 
The Jaccard index is used to quantify the similarity between two datasets. The Jaccard index takes on a value between 0 and 1. An index of 1 means that the two dataset are identical, and an index of 0 indicates that the datasets have no common elements. The Jaccard index is defined by the following formula: 
 
This is simply the number of unique elements common to both sets divided by the total number of unique elements in both sets. 
Fowlkes-Mallows index 
confusion matrix 
A confusion matrix can be used to quickly visualize the results of a classification (or clustering) algorithm.It shows how different a cluster is different from the gold standard cluster. 
[edit] Relative criterion of qualityCluster evaluation methods that incorporate relative criterion directly evaluate the clustering algorithm in regard to user needs. For example, a clustering algorithm may perform admirably based on various internal criterion, but the algorithm may be unnecessarily slow. If the user seeks quick clustering response, a faster algorithm that performs slightly poorer on the internal criterion may be more desirable. This valuation method is more direct and requires carefully defining what the "user's needs" are. This approach can also be more expensive, in particular if large user studies are required to fully understand user preference. [15]

[edit] AlgorithmsIn recent years considerable effort has been put into improving algorithm performance (Z. Huang, 1998)[Full citation needed]. Among the most popular are CLARANS (Ng and Han,1994)[Full citation needed], DBSCAN[18] and BIRCH (Zhang et al., 1996)[Full citation needed].

Several different clustering systems based on mutual information have been proposed. One is Marina Meila's 'Variation of Information' metric; another provides hierarchical clustering[19]. The adjusted-for-chance version for the mutual information is the Adjusted Mutual Information (AMI), which corrects mutual information for agreement solely due to chance between clusterings (Vinh et al., 2009)[Full citation needed].